package com.itheima.datastructure.linkedlist;

/**
 * 根据值删除节点
 */
public class E02Leetcode203 {


    /**
     * 要删除就要知道删除节点的前一个和后一个
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements0(ListNode head, int val) {
        ListNode sentinel = new ListNode(-1, head);
        //前一个节点
        ListNode pre = sentinel;
        //当前节点
        ListNode cur = head;
        while (cur != null) {
            if (val == cur.val) {
                // 删除
                pre.next = cur.next;
                //cur向后移动
                cur = cur.next;
                // pre不变
            } else {
                //cur和pre都向后移动
                cur = cur.next;
                pre = pre.next;
            }

        }
        return sentinel.next;
    }


//----递归"向下"过程 (递归调用阶段)
//    removeElements1(节点1, 1)  // cur.val == 1
//├── RETURN removeElements1(节点2, 1)  // 跳过节点1
//
//    removeElements1(节点2, 1)  // cur.val != 1
//├── lastResult = removeElements1(节点3, 1)
//
//    removeElements1(节点3, 1)  // cur.val != 1
//├── lastResult = removeElements1(节点4, 1)
//
//    removeElements1(节点4, 1)  // cur.val != 1
//├── lastResult = removeElements1(节点5, 1)
//
//    removeElements1(节点5, 1)  // cur.val != 1
//├── lastResult = removeElements1(节点1(末尾), 1)
//
//    removeElements1(节点1(末尾), 1)  // cur.val == 1
//            ├── RETURN removeElements1(NULL, 1)
//
//    removeElements1(NULL, 1)
//├── RETURN NULL  // 基准情况

    //----递归"向上"过程 (回溯返回阶段)
//    removeElements1(NULL, 1)
//└── RETURN NULL
//
//    removeElements1(节点1(末尾), 1)
//            └── RETURN NULL  // 返回上一层的结果
//
//    removeElements1(节点5, 1)
//├── lastResult = NULL
//├── 节点5.next = NULL
//└── RETURN 节点5
//
//    removeElements1(节点4, 1)
//├── lastResult = 节点5
//├── 节点4.next = 节点5
//└── RETURN 节点4
//
//    removeElements1(节点3, 1)
//├── lastResult = 节点4->5
//            ├── 节点3.next = 节点4->5
//            └── RETURN 节点3->4->5
//
//    removeElements1(节点2, 1)
//├── lastResult = 节点3->4->5
//            ├── 节点2.next = 节点3->4->5
//            └── RETURN 节点2->3->4->5
//
//    removeElements1(节点1, 1)
//└── RETURN 节点2->3->4->5  // 直接返回下一层结果，跳过节点1

    /**
     * 删除链表中等于给定值 val 的所有节点，返回删除值后的链表。
     *
     * @param cur
     * @param val
     * @return
     */
    public ListNode removeElements1(ListNode cur, int val) {
        if (null == cur) {
            return null;
        }

        if (cur.val == val) {
            //当前值==目标值，当前cur不要了，返回下一个节点的递归结果
            return removeElements1(cur.next, val);
        } else {
            //拿到下一个节点的递归结果
            ListNode next = removeElements1(cur.next, val);
            //当前的的next = 下一个节点的递归结果
            cur.next = next;
            //返回自身
            return cur;
        }
    }


    /**
     * 方法2
     *
     * @param p   链表头
     * @param val 目标值
     * @return 删除后的链表头
     */
    public ListNode removeElements(ListNode p, int val) {
        if (p == null) {
            return null;
        }
        if (p.val == val) {
            //返回下一个节点的递归结果
            return removeElements(p.next, val);
        } else {
            //返回自身，但是我的next应该更新
            p.next = removeElements(p.next, val);
            return p;
        }
    }

    public ListNode printElements(ListNode p) {
        if (p == null) {
            return null;
        }
        p.next = printElements(p.next);
        return p;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 6, 3, 6);
//        ListNode head = ListNode.of(7, 7, 7, 7);
        System.out.println(head);
        System.out.println(new E02Leetcode203()
                .removeElements1(head, 6));
    }
}
